package com.acwing.partition4;

import java.io.*;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author `RKC`
 * @date 2022/1/17 15:49
 */
public class AC345牛站 {

    private static final int N = 210, INF = 0x3f3f3f3f;
    private static int n = 0, m = 0;
    private static int[][] matrix = new int[N][N], dist = new int[N][N], temp = new int[N][N];
    private static Map<Integer, Integer> map = new HashMap<>();

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] s = reader.readLine().split("\\s+");
        int k = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        int start = Integer.parseInt(s[2]), end = Integer.parseInt(s[3]);
        map.put(start, ++n);
        map.put(end, ++n);
        start = map.get(start);
        end = map.get(end);
        for (int i = 0; i < N; i++) Arrays.fill(matrix[i], INF);
        for (int i = 0; i < m; i++) {
            s = reader.readLine().split("\\s+");
            int w = Integer.parseInt(s[0]), u = Integer.parseInt(s[1]), v = Integer.parseInt(s[2]);
            //离散化设置编号
            if (!map.containsKey(u)) map.put(u, ++n);
            if (!map.containsKey(v)) map.put(v, ++n);
            u = map.get(u);
            v = map.get(v);
            matrix[u][v] = matrix[v][u] = Math.min(matrix[u][v], w);
        }
        qmi(k);
        writer.write(dist[start][end] + "\n");
        writer.flush();
    }

    private static void qmi(int k) {
        for (int i = 0; i <= n; i++) Arrays.fill(dist[i], INF);
        for (int i = 1; i <= n; i++) dist[i][i] = 0;
        //快速幂倍增思想
        while (k > 0) {
            if ((k & 1) == 1) mul(dist, dist, matrix);
            mul(matrix, matrix, matrix);
            k >>= 1;
        }
    }

    private static void mul(int[][] c, int[][] a, int[][] b) {
        for (int i = 0; i < N; i++) Arrays.fill(temp[i], INF);
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    temp[i][j] = Math.min(temp[i][j], a[i][k] + b[k][j]);
                }
            }
        }
        for (int i = 0; i < N; i++) System.arraycopy(temp[i], 0, c[i], 0, N);
    }
}
